Estimation of available bandwidth for an end-to-end network path has potential application in both civilian and military environments. Available bandwidth (AB) is defined as the volume of unused link capacity on the tight link (i.e., link with the least “headroom”) of an end-to-end path and represents the amount of additional traffic a given source can inject into the network without exceeding the link capacity of any given link in the path. Available bandwidth is distinguished from effective bandwidth (EB) which corresponds to the capacity of the narrow link (i.e., smallest capacity link) of the end-to-end path.
Estimation of available bandwidth for an end-to-end network path allows traffic sources to judiciously regulate the volume of application traffic injected into the network. For example, knowing when available bandwidth is small could be used by a source to preempt or deny low priority communication sessions in order to make more link capacity available for higher priority sessions that might otherwise experience degraded performance if congestion was allowed to build. Earlier bandwidth estimation techniques relied on active packet probing to estimate effective bandwidth. However, active packet probing in wireless mobile battlefield networks, for example, can be prohibitively costly in terms of consuming link resources. Furthermore, while packet probing can provide estimates of effective bandwidth, it does not necessarily reveal available bandwidth due to the effect of cross traffic that can not be measured directly.
In existing packet probing methods, back-to-back packets are injected into the network solely for the purpose of estimating the narrow link bandwidth with a significant level of uncertainty. Probing packet pairs are sent into the network, and the dispersion (the difference of arrival time at the destination) is analyzed.
There are major drawbacks and limitations to these packet probing methods. First, the method requires injecting probing packets into the network. Sending probing packets is considered unacceptable in many applications, such as wireless battlefield networks. Second, in the presence of cross traffic, packet probing techniques are effective only if a very large number of probe packets (in some cases, hundreds of packets) are injected into the network. That is, when probe packet techniques rely on isolated packet pair probes, then often the resulting bandwidth estimates will be erroneous due to the packet dispersion modulation effects of cross traffic. Third, previous packet probing techniques only estimate narrow link capacity and do not estimate available bandwidth.
In addition to packet probing methods, there is prior work that proposes means by which to detect shared narrow links but does not compute an actual estimate of available bandwidth. There is also some prior work that estimates available bandwidth, but the techniques of the present invention are distinguished from the earlier work due to their novel heuristics such as the application of fast packets. The techniques of the present invention are novel in that they additionally resolve end-to-end delay (T) into its constituent components: deterministic delay (D), queuing delay (W) and transmission delay (X).
The techniques of the present invention are based on end-to-end delay measurements that do not require active probing and are immune to clock offset. The present approach was initially developed for encrypted wireless networks with strict rules forbidding interactions across a cryptographic boundary between network routers and traffic sources (e.g., red-black networks). While the proposed techniques are described in conjunction with a wireless battlefield context, the techniques are also applicable in wired or wireless commercial networks.